
//2909.元素和最小的山形三元组II
class Solution {
public:
    int minimumSum(vector<int>& nums) {
        //枚举中间值j,分别向两边找最小值
        //在找最小值的时候可以使用前缀和先将从前往后和从后往前的最小值存储起来

        int n=nums.size();
        vector<int> prev(n);   //记录从前往到i位置的最小值
        vector<int> back(n);       //记录从后往前到i位置的最小值
        prev[0]=nums[0],back[n-1]=nums[n-1];
        for(int i=1;i<n;i++) prev[i]=min(prev[i-1],nums[i]);
        for(int i=n-2;i>=0;i--) back[i]=min(back[i+1],nums[i]);

        //遍历j在左边和右边找最小值
        int ret=INT_MAX;
        for(int i=1;i<n-1;i++)
            if(prev[i-1]<nums[i]&&back[i+1]<nums[i]) 
            ret=min(ret,nums[i]+prev[i-1]+back[i+1]);

        return ret==INT_MAX?-1:ret;
    }
};